#include <bits/stdc++.h>
using namespace std;

/*
1255. 得分最高的单词集合
已解答
困难
相关标签
相关企业
提示
你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
单词表 words 中每个单词只能计分（使用）一次。
根据字母得分情况表score，字母 'a', 'b', 'c', ... , 'z' 对应的得分分别为 score[0], score[1], ..., score[25]。
本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。
 

示例 1：

输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。
示例 2：

输入：words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
输出：27
解释：
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。
示例 3：

输入：words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
输出：0
解释：
字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。
 

提示：

1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i] 和 letters[i] 只包含小写的英文字母。
*/

// 法一
class Solution
{
private:
	// 回溯函数，用于尝试所有可能的单词组合
	void backtrack(int idx, vector<int> &count, int current, int &maxScore, const vector<vector<int>> &counts, const vector<int> &scores, const vector<int> &suffixSum)
	{
		// 剪枝：如果当前得分加上剩余最大可能得分不超过当前最大得分，直接返回
		if (current + suffixSum[idx] <= maxScore)
			return;

		// 如果已经处理完所有单词，更新最大得分
		if (idx == counts.size())
		{
			if (current > maxScore)
				maxScore = current;
			return;
		}

		// 不选当前单词，继续处理下一个单词
		backtrack(idx + 1, count, current, maxScore, counts, scores, suffixSum);

		// 尝试选当前单词
		bool canUse = true;
		for (int i = 0; i < 26; ++i)
		{
			// 检查当前单词是否可以使用
			if (counts[idx][i] > count[i])
			{
				canUse = false;
				break;
			}
		}
		if (canUse)
		{
			// 减去当前单词使用的字母
			for (int i = 0; i < 26; ++i)
				count[i] -= counts[idx][i];

			// 增加当前单词得分并递归
			current += scores[idx];
			backtrack(idx + 1, count, current, maxScore, counts, scores, suffixSum);

			// 回溯：恢复当前单词使用的字母和得分
			current -= scores[idx];
			for (int i = 0; i < 26; ++i)
				count[i] += counts[idx][i];
		}
	}

public:
	// 主函数，计算最高得分
	int maxScoreWords(vector<string> &words, vector<char> &letters, vector<int> &score)
	{
		// 统计字母表中每个字母的数量
		vector<int> count(26, 0);
		for (char ch : letters)
			count[ch - 'a']++;

		// 计算每个单词的得分和字母频率
		vector<int> wordScores;
		vector<vector<int>> wordCounts;
		for (const string &word : words)
		{
			vector<int> cnt(26, 0);
			int s = 0;
			for (char ch : word)
			{
				cnt[ch - 'a']++;
				s += score[ch - 'a'];
			}
			wordScores.push_back(s);
			wordCounts.push_back(cnt);
		}

		// 按单词得分从高到低排序
		vector<int> indices(words.size());
		iota(indices.begin(), indices.end(), 0);
		sort(indices.begin(), indices.end(), [&](int a, int b)
			 { return wordScores[a] > wordScores[b]; });

		// 重新排列单词的字母频率和得分
		vector<vector<int>> sortedCounts;
		vector<int> sortedScores;
		for (int i : indices)
		{
			sortedCounts.push_back(wordCounts[i]);
			sortedScores.push_back(wordScores[i]);
		}

		// 计算后缀和，用于剪枝
		int n = words.size();
		vector<int> suffixSum(n + 1, 0);
		for (int i = n - 1; i >= 0; --i)
		{
			suffixSum[i] = suffixSum[i + 1] + sortedScores[i];
		}

		// 初始化最大得分并开始回溯
		int maxScore = 0;
		backtrack(0, count, 0, maxScore, sortedCounts, sortedScores, suffixSum);
		return maxScore;
	}
};

// 法二
class Solution {
	public:
	int ans = 0;
	void dfs(vector<string>& words,vector<int>& cnt,vector<int>& score,int i,int total){
		if(i < 0){
			ans = max(ans,total);
			return;
		}
	   // 不选 words[i]
	   dfs(words,cnt,score,i - 1, total);
	   //选
	   bool flag = true;
	   for(char c : words[i]){
			if(cnt[c - 'a']-- == 0){
				flag = false;
			}
			total += score[c - 'a'];
	   }
	   if(flag){
			dfs(words,cnt,score,i - 1, total);
	   }
		//恢复现场
		for (char c : words[i])
			++cnt[c - 'a'];
	}
	int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
		vector<int> cnt(26,0);
		for(char c : letters){
			cnt[c - 'a']++;
		}
		dfs(words,cnt,score,words.size() - 1,0);
		return ans;
	}
};
